package com.yoshino.leetcode.interview150.bit;

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int al = a.length(), bl = b.length(), n = Math.max(al, bl), carry = 0;
        for (int i = 0; i < n; i++) {
            carry += i < al ? a.charAt(al - i - 1) - '0' : 0;
            carry += i < bl ? b.charAt(bl - i - 1) - '0' : 0;
            sb.append(carry % 2);
            carry /= 2;
        }
        if (carry == 1) {
            sb.append(1);
        }
        return sb.reverse().toString();
    }

    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res = res | (n & 1);
            n >>= 1;
        }
        return res;
    }

    public int hammingWeight(int n) {
        int res = 0;
        for (int i = 0; i < Integer.SIZE; i++) {
            if ((n & 1) == 1) {
                res++;
            }
            n >>>= 1;
        }
        return res;
    }

    public int singleNumber1(int[] nums) {
        // 出现过两次的，取两次异或
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }

    public static void main(String[] args) {
        new Solution().singleNumber(new int[]{2,2,3,2});
    }

    public int singleNumber(int[] nums) {
        // 010  110 -->  00 - 01 - 10 - 00
        int[] bits = new int[Integer.SIZE];
        for (int num : nums) {
            for (int i = 31; i >= 0; i--) {
                bits[i] += (num & 1);
                num >>= 1;
            }
        }
        int res = 0;
        for (int i = 0; i < Integer.SIZE; i++) {
            res <<= 1;
            res |= (bits[i] % 3);
        }
        return res;
    }

    public int rangeBitwiseAnd(int left, int right) {
        // 101 -- 111
        if (left == 0 || left == right) {
            return left;
        }
        // 只需找到公共前綴
        int res = 0;
        for (int i = 0; i < Integer.SIZE; i++) {
            if ((left | right) == left) {
                res = i;
                break;
            }
            left >>>= 1;
            right >>>= 1;
        }
        return (left << res);
    }
}